/**
 * 450. 删除二叉搜索树中的节点
 * https://leetcode-cn.com/problems/delete-node-in-a-bst/
 */
public class Solutions_450 {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(5);
        root.left = new TreeNode(3);
        root.left.left = new TreeNode(2);
        root.left.right = new TreeNode(4);
        root.right = new TreeNode(6);
        root.right.right = new TreeNode(7);
        int key = 3;  // output: {5, 4, 6, 2, null, null, 7}

        TreeNode result = deleteNode(root, key);
        System.out.println(result);
    }

    /**
     * 递归 + 迭代
     * 将要删除的节点，用其左子节点（如果有）代替，其右子节点（如果有），链接到删除节点的前趋节点的右子树上
     */
    public static TreeNode deleteNode2(TreeNode root, int key) {
        if (root == null) {
            return null;
        }
        if (root.val == key) {
            // 找到要删除的节点
            if (root.left == null) {
                // 1. 左子树为空，直接将右子树进行替换
                return root.right;
            } else if (root.right == null) {
                // 2. 右子树为空，直接将左子树进行替换
                return root.left;
            } else {
                // 3. 左右子节点都存在
                TreeNode leftMax = root.left;
                while (leftMax.right != null) {
                    // 3.1 迭代找到前趋节点：左子树中的最右节点
                    leftMax = leftMax.right;
                }
                // 3.2 要删除节点的右子树，成为前趋节点的右子树
                leftMax.right = root.right;
                // 最终要删除节点的左子节点，接替删除节点的位置（原本删除节点的右子树成为了前趋节点的右子树）
                return root.left;
            }
        } else if (root.val < key) {
            // 1. key 大于根节点值，可能在右子树中
            root.right = deleteNode(root.right, key);
        } else {
            // 2. key 小于根节点值，可能在左子树中
            root.left = deleteNode(root.left, key);
        }
        return root;
    }

    /**
     * 递归 + 迭代
     * 将要删除的节点，用其右子节点（如果有）代替，其左子节点（如果有），链接到删除节点的后继节点的左子树上
     */
    public static TreeNode deleteNode(TreeNode root, int key) {
        if (root == null) {
            return null;
        }
        if (root.val == key) {
            // 找到要删除的节点
            if (root.left == null) {
                // 1. 左子树为空，直接将右子树进行替换
                return root.right;
            } else if (root.right == null) {
                // 2. 右子树为空，直接将左子树进行替换
                return root.left;
            } else {
                // 3. 左右子节点都存在
                TreeNode rightMin = root.right;
                while (rightMin.left != null) {
                    // 3.1 找到要删除节点的后继节点：即右子树中的最左节点
                    rightMin = rightMin.left;
                }
                // 3.2 要删除节点的左子树，成为后继节点的左子树（仍然符合二叉搜索树特征）
                rightMin.left = root.left;
                // 最终要删除节点的右子节点，接替删除节点的位置（原本删除节点的左子树成为了后继节点的左子树）
                return root.right;
            }
        } else if (root.val < key) {
            // 1. key 大于根节点值，可能在右子树中
            root.right = deleteNode(root.right, key);
        } else {
            // 2. key 小于根节点值，可能在左子树中
            root.left = deleteNode(root.left, key);
        }
        return root;
    }
}
